package LC;

import java.util.List;

/**
 * Given a non-empty string s and a dictionary wordDict containing a list of non-empty words,
 * determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
 * For example, given
 * s = "leetcode",
 * dict = ["leet", "code"].
 * Return true because "leetcode" can be segmented as "leet code".
 * UPDATE (2017/1/4):
 * The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.
 */
public class LC_139_WordBreak_ArrayList {
    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = List.of("leet", "code");
        boolean f = Solution.wordBreak(s, wordDict);
        boolean f1 = Solution_2.wordBreak(s, wordDict);
        System.out.println(f);
        System.out.println(f1);
    }

    static class Solution {
        static boolean wordBreak(String s, List<String> wordDict) {
            int length = s.length();
            boolean[] words = new boolean[length];
            for (int i = 1; i <= length; i++) {
                int j;
                for (j = 0; j < i; j++) {
                    String substr = s.substring(j, i);
                    if (wordDict.contains(substr) && (j == 0 || words[j - 1])) {
                        words[i - 1] = true;
                        break;
                    }
                }
                if (j == i)
                    words[i - 1] = false;
            }
            return words[length - 1];
        }
    }

    static class Solution_2 {
        static boolean wordBreak(String s, List<String> wordDict) {
            if (s.length() == 0)
                return false;
            if (wordDict.contains(s))
                return true;
            for (int i = 1; i <= s.length(); i++) {
                String substring = s.substring(0, i);
                if (wordDict.contains(substring) && wordBreak(s.substring(i), wordDict))
                    return true;
            }
            return false;
        }
    }
}
